package com.markus.code.剑指offer;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/2 17:28
 * todo: 数组中数字出现的次数
 */
public class SingleNumbers {
    /**
     * 这个题的思路就是所有数进行异或运算，得到的结果，我们做以下处理：
     *      1、先找到最右边第一个1的位置
     *      2、现在有这样一个规定，这个位置上的1就只有两个数的其中一个是1，另一个为0
     */
    public int[] singleNumbers(int[] nums) {
        int []arr = new int[2];
        if(nums == null){
            return arr;
        }
        int ans = nums[0];
        for (int i=1;i<nums.length;i++){
            ans ^= nums[i];
        }
        int firstOne = 1;
        while((firstOne & ans) == 0){
            firstOne = firstOne << 1;
        }
        for (Integer num : nums){
            if ((firstOne & num) == 0){
                arr[0] ^= num;
            }else{
                arr[1] ^= num;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
//        int []arr = {7,1,7,2,6,6,3,1};
        int []arr = {4,1,4,6};
        SingleNumbers demo = new SingleNumbers();
        int[] numbers = demo.singleNumbers(arr);
        System.out.println(numbers[0]+" "+numbers[1]);
    }
}
